\section{Veta o kompaktnosti}

\begin{veta}[O kompaktnosti]
    Nech $T$ je množina formúl jazyka $L$, $A$ je formula $L$. Potom
    $T \models A \iff \exists 
        \mbox{ konečná podmnožina }T'\subseteq T: T' \models A$.
\end{veta}

\begin{dokaz}
    Podľa G\"odelovej vety o úplnosti v predikátovej logike platí
    $T \models A \iff T \provable A$.
    Nech $A_1, A_2, \dots , A_n$ je konečná postupnosť formúl --
    dôkaz $A$. Zoberme $T' = \{B_1, B_2, \dots, B_m\}$, kde $B_i$ sú axiómy
    $T$ nachádzajúce sa v dôkaze $A$.

    Potom môžeme písať $T' \provable A \iff T' \models A$.
    \\
\end{dokaz}

\begin{priklad}
    Na základe vety o kompaktnosti ukážeme, že teóriu telies
    charakteristiky 0 nedokážeme v teórii prvého rádu zapísať
    pomocou konečného počtu axióm.

    Nech $T$ je teória telies charakteristiky 0 (s rovnosťou)
    a jazykom $L=\{0,1,+,*\}$.    
    Označme si pre $p\in N, p\ge 1$ výraz $p \times 1$ ako
    \begin{equation*}
        p \times 1 \equiv \underbrace{1 + (1 + ( 1 + \dots (1 + 1}_{p}) \dots )
    \end{equation*}
    Ďalej si označme formulu $P_p$ ako $P_p: p \times 1 = 0$.
    Pre telesá charakteristiky $p$ platí (z definície charakteristiky)
    \begin{equation*}
     \models \neg P_1 \land \neg P_2 \land \dots \land \neg P_{p-1}
        \land P_p
    \end{equation*}
    Ak teleso nemá konečnú charaktetistiku, tak jeho charakteristika
    je 0.

    Uvažujme formulu $A$ teórie telies charakteristiky 0. Pre $A$ platí
    \begin{equation*}
     T \models A \iff T' \subseteq T, T'\mbox{ konečná}
    \end{equation*}
    Teória $T'$ obsahuje len konečne veľa axióm $\neg P_p$.
    Označme $m$ najväčší index axiomy, ktorá patrí do $T'$.
    Potom formula $A$ je splnená aj vo všetkých telesách dostatočne
    veľkej konečnej charakteristiky 
    (presnejšie povedané charakteristiky $>m$).
    Ak teda formula $A$ je teorémou telies charakteristiky $0$,
    tak platí aj vo všetkých telesách dostatočne veľkej charakteristiky.
    Toto začína napovedať, že čosi nie je na kostolnom poriadku.
    Dotiahnime teda naše argumenty do konca.

    Uvažujme teraz axiómy $A_1, \dots A_n$ teórie telies s
    charakteristikou 0.
    \begin{equation*}
        T' \models A_i \implies T' \models A_1 \land A_2 \land \cdots
        \land A_n \equiv B
    \end{equation*}
    Formula $B$ teda platí vo všetkých telesách charakteristiky 0.
    Lenže ako sme už povedali, tým pádom platí aj vo všetkých telesách
    dostatočnej charakteristiky. To je ale spor, pretože axiómy telies
    charakteristiky 0 nemôžu platiť v telesách konečnej
    charakteristiky.

    Záverom teda je, že logikou prvého rádu nemôžeme 
    konečným počtom axiom charakterizovať teóriu telies.
    V logike prvého rádu totiž kvantifikujeme len individuá.
\end{priklad}

\begin{poznamka}
    Ak zavedieme ďalší druh premenných, prirodzené čísla,
    nekonečne veľa axiom typu $\neg P_p$ môžeme nahradiť jednou formulou:
    \begin{equation*}
        (\forall p)(p\times 1\not=0)
    \end{equation*}
    Toto sa v literatúre terminologicky nazýva
    {\tt slabá logika druhého rádu}. V nej
    vieme konečne axiomatizovať teóriu telies charakteristiky 0.
    Tým pádom 
    {\tt v slabej logike druhého rádu neplatí veta o kompaktnosti}.
\end{poznamka}

\begin{poznamka}
    Poznáme doteraz tieto logiky:
    \begin{itemize}
    \item logika 1. rádu -- premenné len pre indivíduá
    \item logika 2. rádu -- premenné pre množiny indivíduí
    \item slabá logika 2. rádu -- premenné pre indivíduá a prirodzené
        čísla
    \end{itemize}
\end{poznamka}

\medskip \noindent
Mali sme Godelovu vetu v dvoch tvaroch. Prvý bol
$ T \models A \iff T \provable A$, druhý variant znel 
``Teória je bezosporná, keď má model''.
Preto aj veta o kompaktnosti bude mať druhý tvar.

\begin{veta}[2. tvar vety o kompaktnosti]
%%% {{{
    Nech $T$ je množina formúl jazyka $L$. 
    Model teórie $T$ existuje práve vtedy, keď každá konečná podmnožina
    $T' \subseteq T$ má model.
%%% }}}    
\end{veta}

\begin{dokaz}
%%% {{{
    Z 2. G\"odelovej vety vyplýva, že $T$ má model $\iff$ je bezosporná.
    Z lindenbauma zase, že $T$ je bezosporná $\iff$ každá konečná
    $T' \subseteq T$ je bezosporná, čo opäť z G\"odelovou vety
    $\iff$ každá konečná podmnožina $T' \subseteq T$ má model.
    \\
%%% }}}
\end{dokaz}

\begin{priklad}
    Pomocou vety o kompaktnosti tohto tvaru dokážeme zaručiť,
    že pre Peanovu aritmetiku existujú aj neštandardné modely.
    Zopakujme si najskôr jej axiómy:

    \begin{enumerate}
    \item $\provable \neg (S(x) = 0)$
    \item $\provable (S(x) = S(y)) \implies (x=y)$
    \item $\provable (x+0) = x$
    \item $\provable (x+S(y)) = S(x+y)$
    \item $\provable (x * 0) = 0$
    \item $\provable (x * S(y)) = ((x*y)+x)$
    \par \noindent Doteraz sme dostali Robinsonovu aritmetiku. Peanovu
    aritmetiku dostávame pridaním axiómy indukcie:
    \item $\provable A_x[0] \implies (\forall x)\Big(A \implies (
            A_x[S(x)] \implies (\forall x)A)\Big)$
    \end{enumerate}
    Táto aritmetika má model 
    $\mathcal{N} = \langle 0,1,S,+,*,\mathbb{N}_0 \rangle$.

    Ukážeme, že Peanova aritmetika má aj neštandardné modely.
    Definujme množinu ``numerálov'' $\bar{n}$ pre $n\in\mathbb{N}_0$
    ako termoy jazyka $L$ nasledovne:\footnote{Veľmi podobne ako
        Herbrandovské interpretácie, viď príslušnú kapitolu}
    \begin{itemize}
    \item $\bar{0} = 0$
    \item $\overline{n+1} = S(\bar{n}) = 
        \underbrace{S(S( \cdots S}_{(n+1)\mbox{-krát}}(0) \cdots ))$
    \end{itemize}

    K jazyku $L$ zostrojíme rozšírený jazyk $L_c$ tak,
    že do $L$ pridáme konštantu $c$ a
    teóriu rozšírime o axiómy
    \begin{equation*}
        \provable C_n: c \not= \bar{n} \quad\quad \forall n\in\mathbb{N}_0
    \end{equation*}

    Vidíme, že každá konečná podmnožina $T_c$ má model,
    ktorý vznikne expanziou štandardného modelu $\mathcal{N}$.
    Konštantu $c$ budeme jednoducho realizovať ako indivíduom $n$,
    ktoré nepatrí do indivíduí použitých v axiómach (a teda je istým
    spôsobom ``nové'').
    Čiže každá $T' \subseteq T_c$ má model a na základe vety o kompaktnosti 
    aj $T_c$ má model. Teraz si môžeme všimnúť, že model $T_c$ bude rôzny
    od štandardného modelu a nebude s ním ani izomorfný.
    Vieme teda, že neštandardný model existuje, ale nevieme ho skonštruovať.
\end{priklad}
